/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/print-numbers-by-recursion
   @Language: C++
   @Datetime: 16-02-09 08:22
   */

// Method 1, for-loop
class Solution {
public:
	/**
	 * @param n: An integer.
	 * return : An array storing 1 to the largest number with n digits.
	 */
	vector<int> numbersByRecursion(int n) {
		// write your code here
		vector<int> v;
		n=pow(10,n);
		for(int i=1;i<n;v.push_back(i++));
		return v;
	}
};

// Method 2, recursion
class Solution {
	void build(vector<int> &v, int num, int n){
		if(n==0){
			v.push_back(num);
			return;
		}
		for(int a=0; a<10; ++a)
			build(v,num*10+a,n-1);
	}
public:
	/**
	 * @param n: An integer
	 * @return: An array storing 1 to the largest number with n digits.
	 */
	vector<int> numbersByRecursion(int n) {
		// write your code here
		vector<int> v;
		build(v,0,n);
		v.erase(v.begin());
		return v;
	}
};
